#!/usr/bin/python
# -*- coding:utf-8 -*-
#快速排序
#@author : wklken@yeah.net

#基本快速排序
def partition(l, left, right):
    key = l[right]
    index_l = left
    index_r = right
    
    while index_l < index_r:
        while index_l < index_r and l[index_l] <= key:
            index_l += 1
        while index_l < index_r and l[index_r] >= key:
            index_r -= 1
          
        if index_l >= index_r:
            break
        l[index_l], l[index_r] = l[index_r], l[index_l]
    l[right], l[index_r] = l[index_r], l[right]
    return index_r

def quick_sort(l, left, right):
    if left < right:
        key_index = partition(l, left, right)
        print "onetime1,",left,key_index -1
        print "onetime2,",key_index+1, right
        quick_sort(l, left, key_index -1 )
        quick_sort(l, key_index+1, right)

#改进版本




l = [ 50,10,30,20,60,40,35] #,36
#l = [ 20,10,30] #,36
print l
quick_sort(l, 0, len(l)-1 )
print l